/*
    分组背包、完全背包

    前置知识: 
    讲解067、讲解068 - 二维动态规划及其空间压缩技巧
    讲解073 - 01背包、有依赖的背包
    【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统


    分组背包：多个物品分组，每组只能取1件
             每一组的物品都可能性展开就可以了。注意时间复杂度不会升阶，O(物品数量 * 背包容量)

    完全背包：与01背包的区别仅在于 每种商品可以选取无限次。时间复杂度O(物品数量 * 背包容量)

    ================================================

    题目1
    分组背包(模版)
    给定一个正数m表示背包的容量，有n个货物可供挑选
    每个货物有自己的体积(容量消耗)、价值(获得收益)、组号(分组)
    同一个组的物品只能挑选1件，所有挑选物品的体积总和不能超过背包容量
    怎么挑选货物能达到价值最大，返回最大的价值
    测试链接 : https://www.luogu.com.cn/problem/P1757

    ================================================

    题目2
    从栈中取出K个硬币的最大面值和
    一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币
    每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里
    给你一个列表 piles ，其中 piles[i] 是一个整数数组
    分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k
    请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少
    测试链接 : https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/

    ================================================

    题目3
    完全背包(模版)
    给定一个正数t，表示背包的容量
    有m种货物，每种货物可以选择任意个
    每种货物都有体积costs[i]和价值values[i]
    返回在不超过总容量的情况下，怎么挑选货物能达到价值最大
    返回最大的价值
    测试链接 : https://www.luogu.com.cn/problem/P1616

    ================================================

    题目4
    正则表达式匹配
    给你字符串s、字符串p
    s中一定不含有'.'、'*'字符，p中可能含有'.'、'*'字符
    '.' 表示可以变成任意字符，数量1个
    '*' 表示可以让 '*' 前面那个字符数量任意(甚至可以是0个)
    p中即便有'*'，一定不会出现以'*'开头的情况，也一定不会出现多个'*'相邻的情况(无意义)
    请实现一个支持 '.' 和 '*' 的正则表达式匹配
    返回p的整个字符串能不能匹配出s的整个字符串
    测试链接 : https://leetcode.cn/problems/regular-expression-matching/

    ================================================

    题目5
    通配符匹配（和题目4高度相似，只是边界条件不同而已，而且更简单）
    给你字符串s、字符串p
    s中一定不含有'?'、'*'字符，p中可能含有'?'、'*'字符
    '?' 表示可以变成任意字符，数量1个
    '*' 表示可以匹配任何字符串
    请实现一个支持 '?' 和 '*' 的通配符匹配
    返回p的整个字符串能不能匹配出s的整个字符串
    测试链接 : https://leetcode.cn/problems/wildcard-matching/

    ================================================

    题目6
    购买足量干草的最小花费
    有n个提供干草的公司，每个公司都有两个信息
    cost[i]代表购买1次产品需要花的钱
    val[i]代表购买1次产品所获得的干草数量
    每个公司的产品都可以购买任意次
    你一定要至少购买h数量的干草，返回最少要花多少钱
    测试链接 : https://www.luogu.com.cn/problem/P2918

*/